package zuo.algo.c07;

import zuo.algo.data.TreeNode;
import zuo.algo.util.TreeUtils;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 01:48-在二叉树中找一个节点的后继节点
 * 后继节点指中序遍历的后一个节点
 */
public class SuccessorNode {

    public static TreeNode exc1(TreeNode head, TreeNode target) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode node = head;
        boolean isNode = false;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                if (isNode) {
                    return node;
                }
                if (target == node) {
                    isNode = true;
                }
                node = node.right;
            }
        }
        return null;
    }

    public static TreeNode exc2(TreeNode head, TreeNode target) {
        if (target.right != null) {
            TreeNode node = target.right;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }
        TreeNode node = target;
        TreeNode parent = node.parent;
        while (parent != null && parent.left != node) {
            node = parent;
            parent = node.parent;
        }
        return parent;
    }

    public static void main(String[] args) {
        Map<Integer, TreeNode> map = new HashMap<>();
        TreeNode head = TreeUtils.getTree(map);
        TreeNode target = map.get(6);
        TreeNode res1 = exc1(head, target);
        TreeNode res2 = exc2(head, target);
        if (res1 != res2 || res1 != map.get(8)) {
            System.out.println("error:" + res1.val + ":" + res2.val);
        }
        target = map.get(8);
        res1 = exc1(head, target);
        res2 = exc2(head, target);
        if (res1 != res2 || res1 != map.get(10)) {
            System.out.println("error:" + res1.val + ":" + res2.val);
        }
        target = map.get(10);
        res1 = exc1(head, target);
        res2 = exc2(head, target);
        if (res1 != res2 || res1 != map.get(14)) {
            System.out.println("error:" + res1.val + ":" + res2.val);
        }
        target = map.get(14);
        res1 = exc1(head, target);
        res2 = exc2(head, target);
        if (res1 != res2 || res1 != map.get(16)) {
            System.out.println("error:" + res1.val + ":" + res2.val);
        }
        target = map.get(20);
        res1 = exc1(head, target);
        res2 = exc2(head, target);
        if (res1 != res2 || res1 != null) {
            System.out.println("error:" + res1.val + ":" + res2.val);
        }
    }
}
